详解 leetcode 221 题：最大正方形

学好算法没有捷径，最好的捷径就是多刷题，并且跳出舒适区，每道题都要寻找最优解，也不能老是做那些你自己比较擅长的题，不定期更新 Leetcode 的题，每道题都会给出多种解法以及最优解

题目描述

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例

输入: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

解法一：暴力法

在一个二维矩形中，如果我们要确定一个矩阵，我们只需要知道确定它的左上角和右下角就可以了，而正方形相当于边相等的矩阵。这道题暴力法还是比较好做，就是把矩阵中的每一个点，都充当左上角来遍历搜索一下。

例如我刚开始把（0，0）这个点当左上角，然后向右下角搜索

搜索的过程中，用一个变量来记录最大正方形的面积。接着用（0，1）作为左上角，不断着向右下角搜索

当然，（0，1）这个位置本身就是 0 ，所以是没有搜索的必要的，我这里只是做个演示。最终的代码如下（可以左右滑动代码，也可以看图片版代码，下同）

    public int maximalSquare(char[][] matrix) {
        // 如果矩阵长或宽少于1则直接返回0
        if(matrix.length < 1 || matrix[0].length < 1)
            return 0;

        int rows = matrix.length;
        int cols = matrix[0].length;
        // 记录最大边长
        int max = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 把（i，j）作为左上角向右下角搜索
                if (matrix[i][j] == '1') {
                    // 此时正方形的边长
                    int sqlen = 1;
                    boolean flag = true;//记录是否遇到0的位置
                    while (sqlen + i < rows && sqlen + j < cols && flag) {
                        for (int k = j; k <= sqlen + j; k++) {
                            if (matrix[i + sqlen][k] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        for (int k = i; k <= sqlen + i; k++) {
                            if (matrix[k][j + sqlen] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        if (flag)
                            sqlen++;
                    }
                    if (max < sqlen) {
                        max = sqlen;
                    }
                }
            }
        }
        return max * max;
    }

图片版代码：

• 时间复杂度：O((mn)^2)

• 空间复杂度：O(1)

解法二：动态规划

对于动态规划，大部分情况下我们都会定义一个二维数组dp，然后定义dp[i][j] 的含义，接着推导 dp[i][j] 与 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1] 之间的关系。当然，也可以是推导 dp[i][j] 与 dp[i+1][j]、dp[i][j+1]、dp[i+1][j+1] 之间的关系，下面我们讲下用 dp 该怎么解这道题。

1、首先我们定义 dp[i][j] 含义为正方形以 dp[i][j] 作为右下角时的最大边长值。

2、接着我们来推导他们的关系

显然，对于任意一点 dp[i][j]，由于该点是正方形的右下角，所以该点的右边，下边，右下边都不用考虑，关心的是左边，上边，和左上边，也就是我们要推导 dp[i][j] 与 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1] 之间的关系。他们有如下关系

dp[i][j] = min（ dp[i-1][j], dp[i-1][j-1], dp[i][j-1] ） + 1

这个关系其实也不算难推，毕竟不能有 0 存在，所以只能取交他们三个点的交集。你们可以画个图，可能就比较好理解了。

代码如下（可以左右滑动代码，也可以看图片版代码，下同）：

    public int maximalSquare(char[][] matrix) {
        // 如果矩阵长或宽少于1则直接返回0
        if(matrix.length < 1 || matrix[0].length < 1)
            return 0;
        int rows = matrix.length;
        int cols = matrix[0].length;

        int[][] dp = new int[rows + 1][cols + 1];
        int max = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (matrix[i-1][j-1] == '1'){
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        return max * max;
    }

图片版

• 时间复杂度：O(n*m)

• 空间复杂度：O(n*m)

解法三：动态规划优化

用动态规划时，可以说 80% 都是用二维数组，但是 80% 也都可以优化成一维数组，这很容易理解，大家看这个公式

dp[i][j] = min( dp[i-1][j], dp[i-1][j-1], dp[i][j-1] ) + 1

通过上面的公式我们可以知道，我们要算 dp[i][j] 的值时，只需要用到 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 三个值就可以了。也就是说，我们在算矩阵 dp 第 i 行的值时，只需要用第 （i - 1） 行的值，至于（i-2）的值根本就不需要用到

所以我们只需要用一个一维数组就可以了，然后每次算出第 i 行的值，就马上用一维数组 dp[0….n] 把这行值保存起来，供计算 i+1 行时使用。

如下图

new_dp[i] 相当于二维矩阵的 dp[i][j]

dp[i] 相当于 dp[i-1][j]

dp[i-1] 相当于 dp[i-1][j]

pre 相当于 dp[i-1][j-1]。

然后用一维矩阵的话，我们每次计算出 new_dp[i] 后，就马上用 new_dp[i] 覆盖 dp[i] 的值，并且还要用一个变量 pre 来保存dp[i-1][j-1]的值。

好吧，估计你也给我绕晕了，如果不大理解，强烈建议画图模拟一下

最终代码如下（可以左右滑动代码，也可以看图片版代码，下同）

    public int maximalSquare(char[][] matrix) {
        if(matrix.length < 1 || matrix[0].length < 1)
            return 0;

        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] dp = new int[cols + 1];
        int max = 0, prev = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                int temp = dp[j];
                if (matrix[i - 1][j - 1] == '1') {
                    dp[j] = Math.min(Math.min(dp[j - 1], prev), dp[j]) + 1;
                    max = Math.max(max, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = temp;
            }
        }
        return max * max;
    }

图片版

• 时间复杂度：O(n*m)

• 空间复杂度：O(n)

额外话

动态规划是一个比较难的算法思想，特别是对于初学者，遇到动态规划的题基本凉，我刚开始也被搞过，后来能看懂关于动态规划的答案，但是自己写不出，一气之下做了几十道动态规划的题，发现做来做去套路都差不多，于是总结出了自己的一个套路模板，从此 80% 的动态规划题都会做。所以呢，后面找个时间我得写一写我的经验，这个经验适合看得懂动态规划，但又不知道怎么下手的人，不过写这篇文章估计需要挺长时间，所以几时写还没确定，，，，大家也可以学我，直接做 50 道动态规划的题，准稳。

推荐阅读：